package com.lw.leetcode.dp.c;

import com.lw.test.util.Utils;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * c
 * dp
 * 188. 买卖股票的最佳时机 IV
 *
 * @author liw
 * @version 1.0
 * @date 2023/2/3 13:52
 */
public class MaxProfit188 {


    public static void main(String[] args) {
        MaxProfit188 test = new MaxProfit188();

        // 4
//        int k = 2;
//        int[] arr = {1, 2, 3, 4, 5};

        // 11
//        int k = 2;
//        int[] arr = {2, 1, 4, 5, 2, 9, 7};

        // 20
//        int k = 4;
//        int[] arr = {6, 5, 9, 2, 5, 1, 5, 3, 8, 1, 7, 2};

        //
        int k = 100;
        System.out.println(k);
        int[] arr = Utils.getArr(1000, 50, 50);

        int i = test.maxProfit(k, arr);
        System.out.println(i);
    }


    public int maxProfit(int k, int[] prices) {
        int m = prices.length;
        int n = k << 1;
        int[][] arr = new int[m + 1][n];
        int max = 0;
        for (int[] ints : arr) {
            Arrays.fill(ints, Integer.MIN_VALUE);
        }
        for (int i = 0; i < m; i++) {
            int[] lasts = arr[i];
            int[] items = arr[i + 1];
            int p = prices[i];
            items[0] = Math.max(lasts[0], -p);
            int limit = Math.min(n, i + 1);
            for (int j = 1; j < limit; j++) {
                if ((j & 1) == 1) {
                    items[j] = Math.max(lasts[j - 1] + p, lasts[j]);
                    max = Math.max(max, items[j]);
                } else {
                    items[j] = Math.max(lasts[j - 1] - p, lasts[j]);
                }
            }
        }
        return max;
    }

}
